package sort;

/**
 * 归并排序 (递归实现) 前提： 每个元素要有可比性，这里元素必须实现Comparable接口。 基本原理为：1.拆分
 * 假设有N个元素的列表，首先把它拆分成2个或2个 以上的元素组成的新的列表(这里我的新列表长度不超过3)，分别对对它们进行排序。
 * 2.归并。把所有的排好序的子类表两两归并，如此重复，直到归并成一个含N个 元素的有序列表为止 图解：(大于3就继续分解) 大于3 8 7 6 5 4 3
 * 2 1 分|解 | 大于3 8 7 6 5 4 3 2 1 分|解 分|解 | | 小于 3 8 7 6 5 4 3 2 1 排序 7 8 5 6 3 4
 * 1 2 归并 | | 7 8 5 6 3 4 1 2 | | 顺序保存 5 6 7 8 1 2 3 4 | 归并 5 6 7 8 1 2 3 4 |
 * 顺序保存 1 2 3 4 5 6 7 8
 * 
 * @param src
 *            临时中间数组，它是目标数组的拷贝
 * @param target
 *            目标排序数组
 * @param low
 *            需排序的起始索引
 * @param high
 *            需排序的结束索引
 * 
 */
public class MergeSort {
	public static void main(String[] args) {
		String[] a = { "9", "8", "7", "6", "5", "4", "3", "2", "1" };
		Object[] aux = (Object[]) a.clone();
		mergeSort(aux, a);
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

	// 每个拆分的列表元素个数<=3
	private static final int INSERTIONSORT_THRESHOLD = 3;

	/**
	 * 
	 * 归并排序(非递归实现)
	 */
	public static void mergeSort(Object[] src, Object[] dest) {
		int spreCount = INSERTIONSORT_THRESHOLD;
		int low, mid, high;
		int len = src.length;
		if (len <= INSERTIONSORT_THRESHOLD * 2) { // 如果只能划分为两组，直接排序
			sort(dest, 0, len);
			return;
		}
		while (spreCount < len) {
			for (int i = 0; i < len; i = high) { // 依次排序归并相邻两个列表
				low = i;
				high = low + spreCount * 2;
				mid = low + spreCount;
				if (high >= len) {
					high = len;
				}
				int l = high - low;
				if (l <= INSERTIONSORT_THRESHOLD) {
					sort(src, low, high);
					break;
				}

				if (spreCount == 3) { // 所有拆分的列表只进行一次排序
					sort(dest, low, mid);
					sort(dest, mid, high);
				}
				if (l == len) // 最后一次归并把src有次序的赋给dest
					Merge(src, dest, low, mid, high);
				else
					Merge(dest, src, low, mid, high);

			}
			spreCount *= 2;
		}

	}

	// 对拆分的每个列表进行排序
	private static void sort(Object[] dest, int low, int high) {
		for (int i = low; i < high; i++) {
			for (int j = i; j > low; j--) {
				if (((Comparable) dest[j - 1]).compareTo(dest[j]) > 0) {
					swap(dest, j - 1, j);
				}
			}
		}
	}

	// 归并相邻两个列表并保存在dest中
	private static void Merge(Object[] src, Object[] dest, int low, int mid,
			int high) {
		int i = low;
		int p = low; // 第一个列表指针
		int q = mid; // 第二个列表指针
		while (p < mid && q < high) {
			if (((Comparable) src[p]).compareTo(src[q]) <= 0) {
				dest[i++] = src[p++];
			} else {
				dest[i++] = src[q++];
			}
		}
		// 添加剩余的值
		while (p < mid && i < high) {
			dest[i++] = src[p++];
		}
		while (q < high && i < high) {
			dest[i++] = src[q++];
		}

	}

	private static void swap(Object[] x, int a, int b) {
		Object t = x[a];
		x[a] = x[b];
		x[b] = t;
	}
}
